package com.zjsru.oneDay;

/***
 *
 * 有序数组中的单一元素
 * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
 *
 * 请你找出并返回只出现一次的那个数。
 *
 * 输入: nums = [1,1,2,3,3,4,4,8,8]
 * 输出: 2
 *
 *
 */
public class singleNonDuplicate {
    //遍历
//    public int singleNonDuplicate(int[] nums) {
//        int n = nums.length;
//        for (int i = 0; i < n -1 ; i+=2) {
//            if(nums[i] != nums[i + 1]){
//                return nums[i];
//            }
//        }
//        return nums[n-1];
//    }
    //二分法
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid;
            } else {
                if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[r];
    }

    public static void main(String[] args) {
        singleNonDuplicate singleNonDuplicate = new singleNonDuplicate();
        int[] nums = new int[]{1, 1, 3, 3, 4, 4, 5, 8, 8};
        System.out.println(singleNonDuplicate.singleNonDuplicate(nums));
    }
}
